package org.example.sword2offer.primary;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: lynn
 * @Descript: 从上往下打印出二叉树的每个节点，同层节点从左至右打印。
 * 考树的广度优先(层序遍历，只能用链表或者队列)! 深度优先（前序遍历，中序遍历，后序遍历,用递归）
 * @date: 2021/3/10 21:45
 * @version: 1.0
 */
public class Q21_PrintBinaryTree {

    public static void main(String[] args) {
        TreeNode treeNode=new TreeNode(8);
        treeNode.left=new TreeNode(4);
        treeNode.right=new TreeNode(6);
        treeNode.left.left=new TreeNode(2);
        treeNode.left.right=new TreeNode(3);
        treeNode.right.left=new TreeNode(5);
        treeNode.right.right=new TreeNode(7);
        System.out.println(printFromTopToBottom(treeNode));
    }

    public static ArrayList<Integer> printFromTopToBottom(TreeNode root){

        return levelOrder(root);
    }


    // 前序遍历
    private static void preTraversal(ArrayList<Integer> arrayList, TreeNode root){
        if(root == null)
            return;
        arrayList.add(root.val);
        preTraversal(arrayList,root.left);
        preTraversal(arrayList,root.right);
    }

    // 中序遍历
    private static void InTraversal(ArrayList<Integer> arrayList, TreeNode root){
        if(root == null)
            return;
        InTraversal(arrayList,root.left);
        arrayList.add(root.val);
        InTraversal(arrayList,root.right);
    }
    // 后序遍历
    private static void PostTraversal(ArrayList<Integer> arrayList, TreeNode root){
        if(root == null)
            return;
        PostTraversal(arrayList,root.left);
        PostTraversal(arrayList,root.right);
        arrayList.add(root.val);
    }

    // 二分搜索树的层序遍历
    public static ArrayList<Integer> levelOrder(TreeNode root){
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(root == null){
            return res;
        }
        LinkedList<TreeNode> linkedList = new LinkedList();
        linkedList.addLast(root); //fixme push xxx
        while(linkedList.size() > 0){
            //队列中出队后，就是我们当前要访问的元素
            TreeNode node = linkedList.pollFirst(); //fixme pollFirst
            res.add(node.val);
            if(node.left != null){
                linkedList.addLast(node.left); // fixme addLast
            }
            if(node.right != null){
                linkedList.addLast(node.right);// fixme addLast
            }
        }
        return res;
    }


    private static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }
}
